package com.pan.alg.niuke.link;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;


/**
 * 描述
 * 假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。
 * 给定两个这种链表，请生成代表两个整数相加值的结果链表。
 * 数据范围：0 \le n,m \le 10000000≤n,m≤1000000，链表任意值 0 \le val \le 90≤val≤9
 * 要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)
 *
 * 例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。
 */
public class LinkListAdd {

    /**
     *
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */
    public static ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        List<ListNode> listNodes1 = transListNode2List(head1);
        List<ListNode> listNodes2 =transListNode2List(head2);
        List<ListNode> reverseList1 = reverseList(listNodes1);
        List<ListNode> reverseList2 = reverseList(listNodes2);

        List<ListNode> listNodes3 = new ArrayList<>();
        Iterator<ListNode> iterator1 = reverseList1.iterator();
        Iterator<ListNode> iterator2 = reverseList2.iterator();
        while(iterator1.hasNext()||iterator2.hasNext()){
            Integer val;
            if(iterator1.hasNext()&&iterator2.hasNext()){
                 val = iterator1.next().val+iterator2.next().val;
            }else if(iterator1.hasNext()){
                 val = iterator1.next().val;
            }else{
                 val = iterator2.next().val;
            }
            ListNode listNode = new ListNode(val);
            listNodes3.add(listNode);
        }
        ListNode plusNode = null;
        for (int i = 0; i < listNodes3.size(); i++) {
            ListNode listNode = listNodes3.get(i);
            Integer val = listNode.val;
            if(val>=10){
                listNode.val=val%10;
                if((i+1)<listNodes3.size()){
                    ListNode nextNode = listNodes3.get(i + 1);
                    Integer nextNodeVal = nextNode.val;
                    nextNode.val=nextNodeVal+val/10;
                }else{
                     plusNode = new ListNode(val/10);
                }
            }
        }
        if(null!=plusNode){
            listNodes3.add(plusNode);
        }

        ListNode result = transListNode2Link(listNodes3);

        return result;
    }

    private static ListNode transListNode2Link(List<ListNode> listNodes3) {
        ListNode head = listNodes3.get(listNodes3.size()-1);
        for (int i = listNodes3.size()-1; i >0; i--) {
            ListNode listNode = listNodes3.get(i);
            listNode.next=listNodes3.get(i-1);
        }
        return head;
    }

    private static List<ListNode> reverseList(List<ListNode> listNodes2) {
        List<ListNode> list = new ArrayList<>();
        for (int i = listNodes2.size()-1; i >=0; i--) {
            list.add(listNodes2.get(i));
        }
        return list;
    }

    private static List<ListNode> transListNode2List(ListNode head1) {
        List<ListNode> listNodes = new ArrayList<>();
        while(head1!=null){
            listNodes.add(head1);
            head1=head1.next;
        }
        return listNodes;
    }

    public static void main(String[] args) {
        int[] arr1 = {9,3,7};
        int[] arr2 = {6,3};
        ListNode listNode1 = ListNodeUtil.transArr2List(arr1);
        ListNode listNode2 = ListNodeUtil.transArr2List(arr2);
//        List<ListNode> listNodes1 = transListNode2List(listNode1);
//        for (ListNode listNode : listNodes1) {
//            System.out.println(listNode.val);
//        }
        ListNode listNode = addInList(listNode1, listNode2);
        ListNodeUtil.printListNode(listNode);


    }

}
